package digui;

public class _06求a的n次幂 {
    // 设计一个求a的n次幂的高效算法
    public static void main(String[] args) {
        int n = 15;
        int a = 2;
        int res = pow0(a,n);
        int ans = pow1(a,n);
        System.out.println(res);
        System.out.println(ans);
    }
    //让指数每次成倍增长，当指数大于n后，如果还有没计算的n-指数次，递归计算
    private static int pow1(int a, int n) {
        if (n == 0) return 1;
        int res = a;
        int ex = 1;
        while ((ex<<1) <= n){
            res = res * res;
            ex<<=1;
        }
        //差多少次幂没有被计算到
        return res * pow1(a,n-ex);
    }

    //O(n)
    private static int pow0(int a, int n) {
        int res = 1;
        for (int i = 0 ; i < n ; i++){
            res = res * a;
        }
        return res;
    }

    public static int ex(int a, int n) {
        if (n == 0) return 1;
        if (n == 1)
            return a;
        int temp = a; //a 的 1 次方
        int res = 1;
        int exponent = 1;
        while ((exponent << 1) < n) {
            temp = temp * temp;
            exponent = exponent << 1;
        }

        res *= ex(a, n - exponent);

        return res * temp;
    }

    /**
     * 巧算
     * m=1010
     */
    public static long ex2(long n, long m) {
        if (n == 0) return 1;
        long pingFangShu = n; //n 的 1 次方
        long result = 1;
        while (m != 0) {
            //遇1累乘现在的幂
            if ((m & 1) == 1)
                result *= pingFangShu;
            //每移位一次，幂累乘方一次
            pingFangShu = pingFangShu * pingFangShu;
            //右移一位
            m >>= 1;
        }
        return result;
    }
}
